package com.cqs.leetcode.math;

public class Sqrt69 {


    static class Solution {
        public int mySqrt(int x) {
            if (x <= 1) return x;
            return mySqrt(x, 0, x);
        }

        private int mySqrt(int target, int left, int right) {
            if (left > right) return left <= target / left ? left : right;
            if (left == right) return left <= target / left ? left : left - 1;
            int mid = (right - left) / 2 + left;
            int t = target / mid;
            if (t == mid) return mid;
            if (t > mid) return mySqrt(target, mid + 1, right);
            return mySqrt(target, left, mid - 1);
        }
    }

    public int mySqrt(int x) {
        if (x <= 1) return x;
        int left = 0, right = x;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (x / mid == mid) return mid;
            if (x / mid > mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return x / right >= right ? right : right - 1;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Sqrt69 sqrt69 = new Sqrt69();
        for (int i = (1<<20); i < (1 << 30); i++) {
//            if (i % 100 == 0) System.out.println(i);
//            System.out.println(i);
            if (solution.mySqrt(i) != sqrt69.mySqrt(i)) {
                System.err.println(i);
            }
        }
    }

}
